package com.lishem.carl._04string;

/**
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
 * <p>
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * <p>
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：haystack = "sadbutsad", needle = "sad"
 * <p>
 * 输出：0
 * <p>
 * 解释："sad" 在下标 0 和 6 处匹配。
 * <p>
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 * <p>
 * 示例 2：
 * <p>
 * 输入：haystack = "leetcode", needle = "leeto"
 * <p>
 * 输出：-1
 * <p>
 * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 * <p>
 * KMP..
 */
public class _6LetCode28_找出字符串中第一个匹配项的下标 {

    public int strStr(String haystack, String needle) {
        if (haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) {
            return -1;
        }
        char[] ss = haystack.toCharArray();
        char[] ts = needle.toCharArray();
        int[] next = getNext(ts);
        int p1 = 0;
        int p2 = 0;
        while (p1 != ss.length && p2 != ts.length) {
            if (ss[p1] == ts[p2]) {
                p1++;
                p2++;
            } else if (next[p2] == -1) {
                p1++;
            } else {
                p2 = next[p2];
            }
        }
        return p2 == ts.length ? p1 - p2 : -1;

    }

    private int[] getNext(char[] ts) {
        if (ts.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ts.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos != ts.length) {
            if (ts[pos - 1] == ts[cn]) {
                next[pos++] = ++cn;
            } else if (next[cn] == -1) {
                next[pos++] = 0;
            } else {
                cn = next[cn];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        _6LetCode28_找出字符串中第一个匹配项的下标 sol = new _6LetCode28_找出字符串中第一个匹配项的下标();
        System.out.println(sol.strStr("sadbutsad", "sad"));
        System.out.println(sol.strStr("leetcode", "leeto"));
    }
}
